from typing import List


class Solution:
    #* 假设你总是可以到达数组的最后一个位置
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if (n <= 1): return 0
        pos = 0
        steps = 0

        while (pos < n-1):
            i_step = pos+nums[pos]
            max_dist = min(n-1, i_step)
            for i in range(pos+1, min(n-1, i_step)+1):  # 这里 i_step 是拷贝 (或取右值)！可以使用！
                far_reach = min(n-1, i+nums[i])         # min(n-1, i_step) 写成 max_dist 也可以
                if far_reach > max_dist:
                    max_dist = far_reach
                    i_step = i
            pos = i_step
            steps += 1
        
        return steps


if __name__ == "__main__":
    soln = Solution()
    soln.jump([1,2,3])
